#include<cmath>
#include<iostream>
#include<stdlib.h>
#include<cstdlib>
using namespace std;
int comp(const void *a,const void *b)
{
    return ((int*)b)[0]-((int*)a)[0];
}
 
int main() 
{
    int t,n,time,a[21][2],score[21];
    cin>>t;
    for(int i=0;i<t;i++)
    {
       
       cin>>n>>time;
       for(int j=0;j<n;j++)
           cin>>a[j][0]>>a[j][1];
       qsort(a,n,sizeof(int)*2,comp);
       int max,max1=0,total;
       for(int j=0;j<n;j++)
       {
          max=0,total=0;
          for(int i=j;i<n;i++)
         {
          total+=a[i][1];
          max+=a[i][0];
          if(total>time)  {total-=a[i][1];max-=a[i][0];continue;}
         }  
         if(max>max1)  max1=max;
       }
       cout<<max1<<endl;
    } 
   // system("pause");
    return 0;
}
    
    
    
    
    
    
    
    
               
       
        
    
    
    
               
       
        
